package com.darwin.darwinIsometric.pathfinding
{
	import flash.geom.Point;

	/**
	 *	 基于二叉堆的A*寻路算法
	 * @author Roland
	 * 
	 */
	public class AStar
	{
		/**
		 *	8方向 
		 */
		public static const DIRECTION_8:int = 8;
		/**
		 *	4方向 
		 */
		public static const DIRECTION_4:int = 4;
		
		/**
		 * 曼哈顿算法
		 */
		public static const MANHATTAN:String = "manhattan";
		
		/**
		 * 欧几里得 
		 */
		public static const EUCLIDIAN:String = "euclidian";
		
		/**
		 * 对角线
		 */
		public static const DIAGONAL:String = "diagonal";
		//private var _open:Array;
		private var _heuristic:Function;//算法核心函数
		private var _open:BinaryHeap;
		private var _grid:MapGrid;
		private var _endNode:ANode;
		private var _startNode:ANode;
		private var _path:Array;
		private var _direction:int;
		private var _straightCost:Number = 1.0;
		private var _diagCost:Number = Math.SQRT2;
		private var _wallCost:Number = 1000;

		private var nowversion:int = 1;
		/**
		 *	最大允许步数，超过这个步数会强制结束
		 */
		public var maxStep:int = 500;
		
		/**
		 *	当无法找到从起点到终点的完整路径时的策略
		 * <li/>0:停在原地不动
		 * <li/>1:尽可能走到离目的地最近的位置 (消耗更大)
		 */
		public var falseStrategy:int = 0; 
		/**
		 *	实例化一个 二叉堆A*算法
		 * @param grid 地图数据
		 * @param direction 方向
		 * @param algorithm 算法
		 */
		public function AStar(direction:int = AStar.DIRECTION_8,algorithm:String = AStar.EUCLIDIAN){
			_direction = direction;
			if(algorithm == AStar.DIAGONAL)
			{
				_heuristic = diagonal;
			}else if(algorithm == AStar.EUCLIDIAN){
				_heuristic = euclidian2;
			}else{
				_heuristic = manhattan;
			}
		}
		
		private function justMin(x:Object, y:Object):Boolean {
			return x.f < y.f;
		}
		
		/**
		 *	寻路 
		 * @param grid 寻路用的地图
		 * @return 寻路是否成功
		 * 
		 */
		public function findPath(grid:MapGrid):Boolean {
			_endNode = grid.endNode;
			nowversion++;
			_startNode = grid.startNode;
			_grid = grid;
			if(_startNode==null || _endNode==null)return false;
			//_open = [];
			_open = new BinaryHeap(justMin);
			_startNode.g = 0;
			return search();
		}
		
		private function search():Boolean {
			var node:ANode = _startNode;
			node.version = nowversion;
			var numCols:int = _grid.numCols;
			var numRows:int = _grid.numRows;
			var step:int = 0;
			while (node != _endNode){
				var startX:int = Math.max(0, node.x - 1);
				var endX:int = Math.min(numCols - 1, node.x + 1);
				var startY:int = Math.max(0, node.y - 1);
				var endY:int = Math.min(numRows - 1, node.y + 1);
				for (var i:int = startX; i <= endX; i++){
					for (var j:int = startY; j <= endY; j++){
						var test:ANode = _grid.getNode(i,j);
						var cost:Number = calculateCost(node,test);
						if(cost>=_wallCost && falseStrategy == 0)continue;
						var g:Number = node.g + cost;
						var h:Number = _heuristic(test);
						var f:Number = g + h;
						if (test.version == nowversion){
							if (test.f > f){
								test.f = f;
								test.g = g;
								test.h = h;
								test.parent = node;
							}
						}else{
							test.f = f;
							test.g = g;
							test.h = h;
							test.parent = node;
							_open.ins(test);
							test.version = nowversion;
						}
						
					}
					
				}
				if (_open.a.length == 1){
					return false;
				}
				node = _open.pop() as ANode;
				step++;
				if(step > maxStep && falseStrategy==0)
				{
					return false;
				}
			}
			buildPath();
			if(falseStrategy==1)
			{
				for (var k:int = 0; k < _path.length-1; k++) 
				{
					var $n:ANode = _grid.getNode(_path[k].x,_path[k].y);
					var $t:ANode =  _grid.getNode(_path[k+1].x,_path[k+1].y);
					if(calculateCost($n,$t) >= _wallCost)
					{
						_path.splice(k+1);
					}
				}
			}
			return true;
		}
		
		internal function calculateCost(node:ANode,test:ANode):Number
		{
			if (test == node || !test.walkable){
				return _wallCost;
			}
			if (test.x != node.x && test.y != node.y){
				var test2:ANode = _grid.getNode(node.x, test.y);
				if (!test2.walkable){
					return _wallCost;
				}
				test2 = _grid.getNode(test.x, node.y);
				if (!test2.walkable){
					return _wallCost;
				}
			}
			var cost:Number = _straightCost;
			if (!((node.x == test.x) || (node.y == test.y))){
				if (_direction == 4){
					return _wallCost;
				}
				cost = _diagCost;
			}
			return cost;
		}
		
		private function buildPath():void {
			_path = [];
			var node:ANode = _endNode;
			_path.push({"x":node.x + _grid.startX,"y":node.y + _grid.startY,"node":node});
			while (node != _startNode){
				node = node.parent;
				_path.unshift({"x":node.x + _grid.startX,"y":node.y + _grid.startY,"node":node});
			}
		}
		
		private function bresenhamNodes(p1:Point, p2:Point):Array {
			var steep:Boolean = Math.abs(p2.y - p1.y) > Math.abs(p2.x - p1.x);
			if (steep){
				var temp:int = p1.x;
				p1.x = p1.y;
				p1.y = temp;
				temp = p2.x;
				p2.x = p2.y;
				p2.y = temp;
			}
			var stepX:int = p2.x > p1.x ? 1 : (p2.x < p1.x ? -1 : 0);
			var stepY:int = p2.y > p1.y ? 1 : (p2.y < p1.y ? -1 : 0);
			var deltay:Number = (p2.y - p1.y) / Math.abs(p2.x - p1.x);
			var ret:Array = [];
			var nowX:Number = p1.x + stepX;
			var nowY:Number = p1.y + deltay;
			if (steep){
				ret.push(new Point(p1.y, p1.x));
			} else {
				ret.push(new Point(p1.x, p1.y));
			}
			while (nowX != p2.x){
				var fy:int = Math.floor(nowY)
				var cy:int = Math.ceil(nowY);
				if (steep){
					ret.push(new Point(fy, nowX));
				} else {
					ret.push(new Point(nowX, fy));
				}
				if (fy != cy){
					if (steep){
						ret.push(new Point(cy, nowX));
					} else {
						ret.push(new Point(nowX, cy));
					}
				}
				nowX += stepX;
				nowY += deltay;
			}
			if (steep){
				ret.push(new Point(p2.y, p2.x));
			} else {
				ret.push(new Point(p2.x, p2.y));
			}
			return ret;
		}
		
		
		/**
		 *	返回路径(必须先调用findPath方法) 
		 * @return 
		 * 
		 */
		public function get path():Array {
			return _path;
		}

		
		//=============各种算法核心函数================
		//曼哈顿算法
		private function manhattan(node:ANode):Number {
			return Math.abs(node.x - _endNode.x) + Math.abs(node.y - _endNode.y);
		}
		//曼哈顿算法2
		private function manhattan2(node:ANode):Number {
			var dx:Number = Math.abs(node.x - _endNode.x);
			var dy:Number = Math.abs(node.y - _endNode.y);
			return dx + dy + Math.abs(dx - dy) / 1000;
		}
		//欧几里得算法
		private function euclidian(node:ANode):Number {
			var dx:Number = node.x - _endNode.x;
			var dy:Number = node.y - _endNode.y;
			return Math.sqrt(dx * dx + dy * dy);
		}
		
		//欧几里德算法2
		private function euclidian2(node:ANode):Number {
			var dx:Number = node.x - _endNode.x;
			var dy:Number = node.y - _endNode.y;
			return dx * dx + dy * dy;
		}
		
		private var TwoOneTwoZero:Number = 2 * Math.cos(Math.PI / 3);
		//跳棋式欧几里德算法
		private function chineseCheckersEuclidian2(node:ANode):Number {
			var y:int = node.y / TwoOneTwoZero;
			var x:int = node.x + node.y / 2;
			var dx:Number = x - _endNode.x - _endNode.y / 2;
			var dy:Number = y - _endNode.y / TwoOneTwoZero;
			return Math.sqrt(dx * dx + dy * dy);
		}

		//对角线算法 
		private function diagonal(node:ANode):Number {
			var dx:Number = Math.abs(node.x - _endNode.x);
			var dy:Number = Math.abs(node.y - _endNode.y);
			var diag:Number = Math.min(dx, dy);
			var straight:Number = dx + dy;
			return _diagCost * diag + _straightCost * (straight - 2 * diag);
		}
	}
}